Search Results

Documents authored by Krokhin, Andrei

Document
Complete Volume
DOI: 10.4230/DFU.Vol7.15301
DFU, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability, Complete Volume

Authors: Andrei Krokhin and Stanislav Zivny

Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)

Abstract
DFU, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability, Complete Volume
Cite as

The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Collection{DFU.Vol7.15301,
  title =	{{DFU, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability, Complete Volume}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-95977-003-3},
  ISSN =	{1868-8977},
  year =	{2017},
  volume =	{7},
  editor =	{Krokhin, Andrei and Zivny, Stanislav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301},
  URN =		{urn:nbn:de:0030-drops-69752},
  doi =		{10.4230/DFU.Vol7.15301},
  annote =	{Keywords: Nonnumerical Algorithms and Problems}
}
Document
DOI: 10.4230/DFU.Vol7.15301.i
Front Matter, Table of Contents, Preface, List of Authors

Authors: Andrei Krokhin and Stanislav Zivny

Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)

Abstract
Front Matter, Table of Contents, Preface, List of Authors
Cite as

The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InCollection{krokhin_et_al:DFU.Vol7.15301.i,
  author =	{Krokhin, Andrei and Zivny, Stanislav},
  title =	{{Front Matter, Table of Contents, Preface, List of Authors}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{0:i--0:xii},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-95977-003-3},
  ISSN =	{1868-8977},
  year =	{2017},
  volume =	{7},
  editor =	{Krokhin, Andrei and Zivny, Stanislav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.i},
  URN =		{urn:nbn:de:0030-drops-69702},
  doi =		{10.4230/DFU.Vol7.15301.i},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, List of Authors}
}
Document
DOI: 10.4230/DFU.Vol7.15301.1
Polymorphisms, and How to Use Them

Authors: Libor Barto, Andrei Krokhin, and Ross Willard

Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)

Abstract
This article describes the algebraic approach to Constraint Satisfaction Problem that led to many developments in both CSP and universal algebra. No prior knowledge of universal algebra is assumed.
Cite as

Libor Barto, Andrei Krokhin, and Ross Willard. Polymorphisms, and How to Use Them. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 1-44, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InCollection{barto_et_al:DFU.Vol7.15301.1,
  author =	{Barto, Libor and Krokhin, Andrei and Willard, Ross},
  title =	{{Polymorphisms, and How to Use Them}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{1--44},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-95977-003-3},
  ISSN =	{1868-8977},
  year =	{2017},
  volume =	{7},
  editor =	{Krokhin, Andrei and Zivny, Stanislav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.1},
  URN =		{urn:nbn:de:0030-drops-69595},
  doi =		{10.4230/DFU.Vol7.15301.1},
  annote =	{Keywords: Constraint satisfaction, Complexity, Universal algebra, Polymorphism}
}
Document
DOI: 10.4230/DFU.Vol7.15301.233
The Complexity of Valued CSPs

Authors: Andrei Krokhin and Stanislav Zivny

Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)

Abstract
We survey recent results on the broad family of problems that can be cast as valued constraint satisfaction problems (VCSPs). We discuss general methods for analysing the complexity of such problems, give examples of tractable cases, and identify general features of the complexity landscape.
Cite as

Andrei Krokhin and Stanislav Zivny. The Complexity of Valued CSPs. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 233-266, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InCollection{krokhin_et_al:DFU.Vol7.15301.233,
  author =	{Krokhin, Andrei and Zivny, Stanislav},
  title =	{{The Complexity of Valued CSPs}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{233--266},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-95977-003-3},
  ISSN =	{1868-8977},
  year =	{2017},
  volume =	{7},
  editor =	{Krokhin, Andrei and Zivny, Stanislav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.233},
  URN =		{urn:nbn:de:0030-drops-69665},
  doi =		{10.4230/DFU.Vol7.15301.233},
  annote =	{Keywords: Constraint satisfaction problems, Optimisation, Tractability}
}
Document
DOI: 10.4230/DagRep.5.7.22
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301)

Authors: Andrei A. Bulatov, Venkatesan Guruswami, Andrei Krokhin, and Dániel Marx

Published in: Dagstuhl Reports, Volume 5, Issue 7 (2016)

Abstract
During the past two decades, an impressive array of diverse methods from several different mathematical fields, including algebra, logic, mathematical programming, probability theory, graph theory, and combinatorics, have been used to analyze both the computational complexity and approximabilty of algorithmic tasks related to the constraint satisfaction problem (CSP), as well as the applicability/limitations of algorithmic techniques. This research direction develops at an impressive speed, regularly producing very strong and general results. The Dagstuhl Seminar 15301 "The Constraint Satisfaction Problem: Complexity and Approximability" was aimed at bringing together researchers using all the different techniques in the study of the CSP, so that they can share their insights obtained during the past three years. This report documents the material presented during the course of the seminar.
Cite as

Andrei A. Bulatov, Venkatesan Guruswami, Andrei Krokhin, and Dániel Marx. The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301). In Dagstuhl Reports, Volume 5, Issue 7, pp. 22-41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{bulatov_et_al:DagRep.5.7.22,
  author =	{Bulatov, Andrei A. and Guruswami, Venkatesan and Krokhin, Andrei and Marx, D\'{a}niel},
  title =	{{The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301)}},
  pages =	{22--41},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{5},
  number =	{7},
  editor =	{Bulatov, Andrei A. and Guruswami, Venkatesan and Krokhin, Andrei and Marx, D\'{a}niel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.5.7.22},
  URN =		{urn:nbn:de:0030-drops-56714},
  doi =		{10.4230/DagRep.5.7.22},
  annote =	{Keywords: Constraint satisfaction problem (CSP), Computational complexity, CSP dichotomy conjecture, Hardness of approximation, Unique games conjecture, Fixed-parameter tractability, Descriptive complexity, Universal algebra, Logic, Decomposition methods}
}
Document
DOI: 10.4230/DagRep.2.11.1
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451)

Authors: Johan Hastad, Andrei Krokhin, and Dániel Marx

Published in: Dagstuhl Reports, Volume 2, Issue 11 (2013)

Abstract
During the past two decades, an impressive array of diverse methods from several different mathematical fields, including algebra, logic, analysis, probability theory, graph theory, and combinatorics, have been used to analyze both the computational complexity and approximabilty of algorithmic tasks related to the constraint satisfaction problem (CSP), as well as the applicability/limitations of algorithmic techniques. The Dagstuhl Seminar 12451 ``The Constraint Satisfaction Problem: Complexity and Approximability'' was aimed at bringing together researchers using all the different techniques in the study of the CSP, so that they can share their insights. This report documents the material presented during the course of the seminar.
Cite as

Johan Hastad, Andrei Krokhin, and Dániel Marx. The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451). In Dagstuhl Reports, Volume 2, Issue 11, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{hastad_et_al:DagRep.2.11.1,
  author =	{Hastad, Johan and Krokhin, Andrei and Marx, D\'{a}niel},
  title =	{{The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451)}},
  pages =	{1--19},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{2},
  number =	{11},
  editor =	{Hastad, Johan and Krokhin, Andrei and Marx, D\'{a}niel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.2.11.1},
  URN =		{urn:nbn:de:0030-drops-39764},
  doi =		{10.4230/DagRep.2.11.1},
  annote =	{Keywords: Constraint satisfaction problem (CSP); Computational complexity; CSP dichotomy conjecture; Hardness of approximation; Unique games conjceture; Fixed-parameter tractability; Descriptive complexity; niversal algebra; Logic; Decomposition methods}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2467
The Complexity of the List Homomorphism Problem for Graphs

Authors: László Egri, Andrei Krokhin, Benoit Larose, and Pascal Tesson

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
We completely classify the computational complexity of the list $\bH$-colouring problem for graphs (with possible loops) in combinatorial and algebraic terms: for every graph $\bH$ the problem is either NP-complete, NL-complete, L-complete or is first-order definable; descriptive complexity equivalents are given as well via Datalog and its fragments. Our algebraic characterisations match important conjectures in the study of constraint satisfaction problems.
Cite as

László Egri, Andrei Krokhin, Benoit Larose, and Pascal Tesson. The Complexity of the List Homomorphism Problem for Graphs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 335-346, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{egri_et_al:LIPIcs.STACS.2010.2467,
  author =	{Egri, L\'{a}szl\'{o} and Krokhin, Andrei and Larose, Benoit and Tesson, Pascal},
  title =	{{The Complexity of the List Homomorphism Problem for Graphs}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{335--346},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2467},
  URN =		{urn:nbn:de:0030-drops-24675},
  doi =		{10.4230/LIPIcs.STACS.2010.2467},
  annote =	{Keywords: Graph homomorphism, constraint satisfaction problem, complexity, universal algebra, Datalog}
}
Document
DOI: 10.4230/DagSemProc.09441.1
09441 Abstracts Collection – The Constraint Satisfaction Problem: Complexity and Approximability

Authors: Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, and Andrei Krokhin

Published in: Dagstuhl Seminar Proceedings, Volume 9441, The Constraint Satisfaction Problem: Complexity and Approximability (2010)

Abstract
From 25th to 30th October 2009, the Dagstuhl Seminar 09441 ``The Constraint Satisfaction Problem: Complexity and Approximability'' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, and Andrei Krokhin. 09441 Abstracts Collection – The Constraint Satisfaction Problem: Complexity and Approximability. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Seminar Proceedings, Volume 9441, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{bulatov_et_al:DagSemProc.09441.1,
  author =	{Bulatov, Andrei A. and Grohe, Martin and Kolaitis, Phokion G. and Krokhin, Andrei},
  title =	{{09441 Abstracts Collection – The Constraint Satisfaction Problem: Complexity and Approximability}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9441},
  editor =	{Andrei A. Bulatov and Martin Grohe and Phokion G. Kolaitis and Andrei Krokhin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09441.1},
  URN =		{urn:nbn:de:0030-drops-23710},
  doi =		{10.4230/DagSemProc.09441.1},
  annote =	{Keywords: Constraint satisfaction problem (CSP), satisfiability, computational complexity, CSP dichotomy conjecture, hardness of approximation, unique games conjecture, universal algebra, logic}
}
Document
DOI: 10.4230/DagSemProc.09441.2
09441 Executive Summary – The Constraint Satisfaction Problem: Complexity and Approximability

Authors: Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, and Andrei Krokhin

Published in: Dagstuhl Seminar Proceedings, Volume 9441, The Constraint Satisfaction Problem: Complexity and Approximability (2010)

Abstract
The seminar brought together forty researchers from di®erent highly advanced areas of constraint satisfaction and with complementary ex- pertise (logical, algebraic, combinatorial, probabilistic aspects). The list of participants contained both senior and junior researchers and a small number of advanced graduate students.
Cite as

Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, and Andrei Krokhin. 09441 Executive Summary – The Constraint Satisfaction Problem: Complexity and Approximability. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Seminar Proceedings, Volume 9441, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{bulatov_et_al:DagSemProc.09441.2,
  author =	{Bulatov, Andrei A. and Grohe, Martin and Kolaitis, Phokion G. and Krokhin, Andrei},
  title =	{{09441 Executive Summary – The Constraint Satisfaction Problem: Complexity and Approximability}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9441},
  editor =	{Andrei A. Bulatov and Martin Grohe and Phokion G. Kolaitis and Andrei Krokhin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09441.2},
  URN =		{urn:nbn:de:0030-drops-23706},
  doi =		{10.4230/DagSemProc.09441.2},
  annote =	{Keywords: Constraint satisfaction problem (CSP), satisfiability, computational complexity, CSP dichotomy conjecture, hardness of approximation, unique games conjecture, universal algebra, logic}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact